\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}

\usepackage{stilo}
\usepackage[boxed,vlined,titlenumbered]{algorithm2e}
\usepackage{color}
%opening
\title{Redes Adhoc e Teoria dos Jogos}
\author{André}
%\date{}

%Distribuicoes mais velhas de Latex precisam deste comando para compilar
\newcommand{\DontPrintSemicolon}{\dontprintsemicolon}


\begin{document}

\maketitle

\section{Modelo de Redes Adhoc}

Uma rede adhoc móvel é  (modelar algo do tipo um grafo $G_t$, onde $t$ é um instante de tempo, pois o grafo atualiza a todo instante)

\begin{ideia}
Ver como definem redes adhoc em artigos da área.
\end{ideia}

Seja $M$ o conjunto dos nós \emph{maliciosos}. Neste modelo, os nós maliciosos invertem a informação passada a alguém que pediu.

\section{Modelagem em Teoria dos Jogos}

Na modelagem de jogos, os \emph{jogadores} são os nodos $V$ da rede adhoc móvel. Cada jogador $i \in V$ tem um \emph{conjunto de estratégias} $S_i$. Uma \emph{estratégia}  $s_i = (s^1_i, \ldots, s^n_i) \in S_i$ do jogador $i$ é um vetor binário de tamanho $n=|V|$, onde $s^j_i = 1$ se $i$ \emph{confia} no jogador $j$, $s^j_i=0$ caso contrário. Assumimos que $s^i_i=1$.    

\begin{ideia}
Uma possível fraqueza do nó malicioso (i.e., torna mais fácil de detectá-lo) é que ele não pode mentir sobre confiar em si mesmo. Ou seja $s_i^i=1$ sempre.
\end{ideia}

Para definir o \emph{payoff} de um jogador $i$, intuitivamente podemos pensar que $i$ terá um comportamento de ``imitação'' dos votos de confiança para um jogador $j$. Desta forma, por exemplo, se $j$ recebe muitos votos de confiança dos outros jogadores, então $i$ receberá um payoff alto se ele escolher confiar em $j$, caso contrário, receberá um payoff baixo.

Suponha que o jogador $i$ consegue obter informação sobre as estratégias de $k$ outros jogadores. Sejam $s_{l_1}, s_{l_2}, \ldots, s_{l_k}$ as $k$ estratégias recebidas. A fração dos $k$ jogadores que confiam num jogador $j$ é
\[
\gamma = \frac{1}{k}\left( s^j_{l_1} + s^j_{l_2}+  \ldots +  s^j_{l_k}\right)
\]
O \emph{payoff} de um jogador $i$ em relação a um jogador $j$ é uma função $p_i^j: S_1 \times \ldots \times S_n \rightarrow \mathbb{R}$, definida da seguinte forma:
\[
p_i^j = s_i^j \cdot \gamma + (1-s_i^j)\cdot (1-\gamma).
\]
Note que, se $s_i^j=1$ então $i$ confia em $j$ e, neste caso, $p_i^j = \gamma$. Isto significa que o payoff de $i$ com relação a $j$ é igual à fração de jogadores que informaram confiar em $j$. Caso contrário, se $s_i^j=0$ então $i$ não confia em $j$ e, neste caso, $p_i^j = 1- \gamma$. Isto significa que o payoff de $i$ com relação a $j$ igual à fração de jogadores que informaram não confiar em $j$. Como $i$ quer maximizar seu payoff com relação a $j$, se $\gamma$ é alta, ele faz $s_i^j=1$; se $\gamma$ é baixo, ele faz $s_i^j=0$. Assim, este payoff simula o comportamento de ``imitar'' a opinião da maioria.

\begin{ideia}
Não precisamos necessariamente considerar que $s_i^j$ é $0$ ou $1$. Podemos fazer com que $s_i^j \in [0,1]$, ou seja, o jogador $i$ agora pode ter uma confiança probabilística em relação a $j$, tornando o modelo mais genérico. Neste caso, para maximizar o payoff, basta derivar e igualar a zero, obtendo que $\gamma = 1/2$. Em outras palavras, se $\gamma=1/2$, o jogador $i$ pode escolher qualquer estratégia que ele terá o mesmo payoff e estará satisfeito com a estratégia escolhida. Em particular, se ele escolher a estratégia $s_i^j=1/2$ ele estará satisfeito. Portanto, se todos os jogadores escolherem a estratégia $1/2$, o jogo estará em \textbf{equilíbrio de Nash misto}. Neste caso, o equilíbrio de Nash é extremamente perigoso, pois gera uma situação estável onde nenhum jogador tem opinião formada sobre a confiança de nenhum outro jogador. É possível caminhar sequencialmente para esse tipo de equilíbrio?   
\end{ideia}

O \emph{payoff} de um jogador $i$ é uma função $p_i: S_1 \times \ldots \times S_n \rightarrow \mathbb{R}$, definida da seguinte forma:
\[
p_i = \sum_{j=0}^{n}p_i^j. 
\]

\begin{duvida}
Verificar qual seria o payoff $p_i^j$ se $i$ ainda não obteve informações sobre $j$. Esse payoff não pode ser o mínimo, nem o máximo. Deve estar no meio, ser neutro. Ajustar as definições conforme necessário.
\end{duvida}

\begin{duvida}
Como tratar o tamanho do vetor da estratégia se o nodos estão sempre entrando e saindo da rede?
\end{duvida}

\begin{duvida}
Como os nodos sabem se entrou (saiu) nodos da rede?
\end{duvida}

\begin{ideia}
Não é necessário considerar um ``jogo completo'', onde todos devem ter opiniões sobre confiar ou não em todos os outros. Basta fixarmos um $j$ e escrevermos o resto do artigo baseado nele (irá simplificar as contas e notação, mas deve-se provar que as coisas se comportam de maneira independente)
\end{ideia}

PRÓXIMA COISA: (1) Verificar como é obtido o equilíbrio de Nash puro (2) Mostrar um contra-exemplo onde a disseminação de informações erradas pode contaminar a rede toda (3) Pensar em algum modelo mais direto para verificar a confiabilidade de um nó para não recairmos no problema 2.  (4) Mostrar que aquela ideia do Albini de ``se um confia, e se o outro confia, então tem algo errado'' pode ser uma falácia.

\end{document}
